package p1100;

import java.util.ArrayDeque;
import java.util.Queue;

public class Leetcode_1162 {
    public int maxDistance(int[][] grid) {
        // 建立四周的坐标系。一次循环玩
        // 这个有点66的。只得学习
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};

        Queue<int[]> land = new ArrayDeque<>();
        int l = grid.length;
        // 所有的陆地入列
        for (int i = 0; i < l; i++) {
            for (int j = 0; j < l; j++) {
                if (grid[i][j] == 1) {
                    land.offer(new int[]{i, j});
                }
            }
        }
        // 从各个陆地开始，一圈一圈的遍历海洋，变成陆地入列，最后遍历到的格子，就是和陆地最远的一块
        int[] p = null;
        boolean hasOcean = false;
        while (!land.isEmpty()) {
            p = land.poll();
            int x = p[0], y = p[1];
            // 这个点四周的海洋入列
            for (int i = 0; i < 4; i++) {
                int newX = x + dx[i];
                int newY = y + dy[i];
                // 如果碰到边界。或者已经是陆地的。跳过
                if (newX < 0 || newX >= l || newY < 0 || newY >= l || grid[newX][newY] != 0) {
                    continue;
                } else {
                    // 在基准点的基础上加1，得到遍历的轮数
                    grid[newX][newY] = grid[x][y] + 1;
                    hasOcean = true;
                    land.offer(new int[]{newX, newY});
                }
            }
        }
        if (p == null || !hasOcean) {
            return -1;
        }
        return grid[p[0]][p[1]] - 1;
    }

    public static void main(String[] args) {

    }
}
